def generate_fat_tree(k):
    if k % 2 != 0:
        raise ValueError("k must be an even number")

    # 数据结构初始化
    links = []  # 链路列表
    switches = {}  # 交换机配置字典
    hosts = {}  # 主机配置字典
    port_counters = {}  # 交换机端口计数器
    switch_id_counter = 0  # 交换机ID计数器
    host_id_counter = 0  # 主机ID计数器

    # 生成核心层交换机
    core_switches = []
    core_count = (k // 2) ** 2
    for i in range(core_count):
        sw_name = f"c{i}"
        core_switches.append(sw_name)
        port_counters[sw_name] = 1
        switches[sw_name] = {"cli_input": f"tree-topo/{sw_name}-runtime.txt"}
        switch_id_counter += 1

    # 处理每个pod
    for pod in range(k):
        # 生成pod内的交换机
        agg_switches = [f"s{pod}-a{i}" for i in range(k // 2)]
        edge_switches = [f"s{pod}-e{i}" for i in range(k // 2)]

        # 初始化pod内交换机
        for sw in agg_switches + edge_switches:
            port_counters[sw] = 1
            switches[sw] = {"cli_input": f"tree-topo/{sw}-runtime.txt"}
            switch_id_counter += 1

        # 1. 连接汇聚层和边缘层（pod内部）
        for agg_sw in agg_switches:
            for edge_sw in edge_switches:
                # 获取当前端口号并递增
                agg_port = port_counters[agg_sw]
                edge_port = port_counters[edge_sw]
                port_counters[agg_sw] += 1
                port_counters[edge_sw] += 1

                # 添加连接
                links.append([f"{agg_sw}-p{agg_port}", f"{edge_sw}-p{edge_port}"])

        # 2. 连接汇聚层和核心层
        for i, agg_sw in enumerate(agg_switches):
            # 计算该汇聚交换机连接的核心交换机组
            core_group_start = i * (k // 2)
            for j in range(k // 2):
                core_sw = core_switches[core_group_start + j]

                # 获取当前端口号并递增
                agg_port = port_counters[agg_sw]
                core_port = port_counters[core_sw]
                port_counters[agg_sw] += 1
                port_counters[core_sw] += 1

                # 添加连接
                links.append([f"{agg_sw}-p{agg_port}", f"{core_sw}-p{core_port}"])

        # 3. 连接边缘层和主机
        for edge_idx, edge_sw in enumerate(edge_switches):
            for host_idx in range(k // 2):
                # 获取当前端口号并递增
                edge_port = port_counters[edge_sw]
                port_counters[edge_sw] += 1

                # 主机信息
                host_name = f"h{host_id_counter}"
                host_ip = f"10.{pod}.{edge_idx}.{host_idx + 11}/24"
                host_mac = f"00:00:00:{pod:02x}:{edge_idx:02x}:{host_idx+11:02x}"

                # 网关信息 (边缘交换机的IP和MAC)
                gateway_ip = f"10.{pod}.{edge_idx}.10"
                gateway_mac = f"00:00:{pod:02x}:{edge_idx:02x}:{edge_port:02x}:00"

                # 添加主机配置
                hosts[host_name] = {
                    "ip": host_ip,
                    "mac": host_mac,
                    "commands": [
                        f"route add default gw {gateway_ip} dev eth0",
                        f"arp -i eth0 -s {gateway_ip} {gateway_mac}",
                    ],
                }

                # 添加连接
                links.append([host_name, f"{edge_sw}-p{edge_port}"])
                host_id_counter += 1

    return links, hosts, switches


# 生成拓扑 (k=4)
k = 4
fat_tree_links, hosts_dict, switches_dict = generate_fat_tree(k)

# 输出二维数组链路
print("Links: [")
for i, link in enumerate(fat_tree_links):
    suffix = "," if i < len(fat_tree_links) - 1 else ""
    print(f"  {link}{suffix}")
print("]")

# 输出主机配置
print("\nHosts: {")
for host, config in hosts_dict.items():
    print(f'    "{host}": {{')
    print(f'        "ip": "{config["ip"]}",')
    print(f'        "mac": "{config["mac"]}",')
    print('        "commands": [')
    for cmd in config["commands"]:
        print(f'            "{cmd}"' + ("," if cmd != config["commands"][-1] else ""))
    print("        ]")
    print("    }" + ("," if host != list(hosts_dict.keys())[-1] else ""))
print("}")

# 输出交换机配置
print("\nSwitches: {")
for switch, config in switches_dict.items():
    print(f'    "{switch}": {{')
    print(f'        "cli_input": "{config["cli_input"]}"')
    print("    }" + ("," if switch != list(switches_dict.keys())[-1] else ""))
print("}")
